// https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            int flag = 0;
            int minNum = INT_MAX;
            for (int j = 0; j < coins.size(); j++) {
                int idx = i - coins[j];
                if (idx >= 0 && dp[idx] != -1) {
                    flag = 1;
                    minNum = min(minNum, dp[idx] + 1);
                }
            }
            
            dp[i] = flag ? minNum : -1;
        }

        return dp[amount];
    }
};